{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #4Sum II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: fourSumCount"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #四数相加 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你四个整数数组 <code>nums1</code>、<code>nums2</code>、<code>nums3</code> 和 <code>nums4</code> ，数组长度都是 <code>n</code> ，请你计算有多少个元组 <code>(i, j, k, l)</code> 能满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= i, j, k, l &lt; n</code></li>\n",
    "\t<li><code>nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "两个元组如下：\n",
    "1. (0, 0, 0, 1) -&gt; nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0\n",
    "2. (1, 1, 0, 0) -&gt; nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>&nbsp; <strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums1.length</code></li>\n",
    "\t<li><code>n == nums2.length</code></li>\n",
    "\t<li><code>n == nums3.length</code></li>\n",
    "\t<li><code>n == nums4.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 200</code></li>\n",
    "\t<li><code>-2<sup>28</sup> &lt;= nums1[i], nums2[i], nums3[i], nums4[i] &lt;= 2<sup>28</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [4sum-ii](https://leetcode.cn/problems/4sum-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [4sum-ii](https://leetcode.cn/problems/4sum-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2]\\n[-2,-1]\\n[-1,2]\\n[0,2]', '[0]\\n[0]\\n[0]\\n[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "  def fourSumCount(self, A, B, C, D):\n",
    "    \"\"\" \n",
    "    :type A: List[int]\n",
    "    :type B: List[int]\n",
    "    :type C: List[int]\n",
    "    :type D: List[int]\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    abCount = Counter( ( a + b ) for a in A for b in B )\n",
    "    cdCount = Counter( ( c + d ) for c in C for d in D )\n",
    "\n",
    "    n = 0\n",
    "    for ab in abCount:\n",
    "      if -ab in cdCount:\n",
    "        n += abCount[ ab ] * cdCount[ -ab ]\n",
    "\n",
    "    return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:\n",
    "        \n",
    "        # checkup = collections.defaultdict(int)\n",
    "        # n = len(nums1)\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         if checkup[nums1[i]+nums2[j]] == 0 :\n",
    "        #             checkup[nums1[i]+nums2[j]]=1\n",
    "        #         else:\n",
    "        #             checkup[nums1[i]+nums2[j]]+=1\n",
    "        countAB = collections.Counter(u + v for u in nums1 for v in nums2)\n",
    "        \n",
    "        ans = 0\n",
    "        for u in nums3:\n",
    "            for v in nums4:\n",
    "                if -u -v in countAB:\n",
    "                    ans += countAB[-u-v]\n",
    "        return ans\n",
    "        \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:\n",
    "        record = dict()\n",
    "        times = 0\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                if i+j in record:\n",
    "                    record[i+j] += 1\n",
    "                else:\n",
    "                    record[i+j] = 1\n",
    "        for i in nums3:\n",
    "            for j in nums4:\n",
    "                key = 0 - i - j\n",
    "                if key in record:\n",
    "                    times += record[key]\n",
    "        return times\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1, nums2, nums3, nums4) -> int:\n",
    "        n = len(nums1)\n",
    "        ans = 0\n",
    "        count = dict()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                t = nums1[i] + nums2[j]\n",
    "                if t not in count:\n",
    "                    count[t] = 0\n",
    "                count[t] += 1\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                x = nums3[i] + nums4[j]\n",
    "                if -x in count:\n",
    "                    ans += count[-x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:\n",
    "        record = {}\n",
    "        for n1 in nums1:\n",
    "            for n2 in nums2:\n",
    "                if n1 + n2 in record:\n",
    "                    record[n1 + n2] += 1\n",
    "                else:\n",
    "                    record[n1 + n2] = 1\n",
    "        count = 0\n",
    "        for n3 in nums3:\n",
    "            for n4 in nums4:\n",
    "                if - n3 - n4 in record:\n",
    "                    count += record[- n3 - n4]\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:\n",
    "        n1=dict()\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                if i+j in n1.keys():\n",
    "                    n1[i+j]=n1[i+j]+1\n",
    "                else:\n",
    "                    n1[i+j]=1\n",
    "        n2=dict()\n",
    "        for i in nums3:\n",
    "            for j in nums4:\n",
    "                if i+j in n2.keys():\n",
    "                    n2[i+j]=n2[i+j]+1\n",
    "                else:\n",
    "                    n2[i+j]=1\n",
    "        s=0\n",
    "        for i in n1.keys():\n",
    "            for j in n2.keys():\n",
    "                if i+j==0:\n",
    "                    s=s+n1[i]*n2[j]\n",
    "        print(n1,n2)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:\n",
    "        rec, cnt = defaultdict(lambda : 0), 0\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                rec[i+j] += 1\n",
    "        for i in nums3:\n",
    "            for j in nums4:\n",
    "                cnt += rec.get(-(i+j), 0) \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:\n",
    "        dic = dict()\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                if i+j in dic:\n",
    "                    dic[i+j]+=1\n",
    "                else:\n",
    "                    dic[i+j] = 1\n",
    "        \n",
    "        count = 0\n",
    "        for i in nums3:\n",
    "            for j in nums4:\n",
    "                if -i-j in dic:\n",
    "                    count+=dic[-i-j]\n",
    "        \n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:\n",
    "\n",
    "        hashmap = dict()\n",
    "\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                if i+j in hashmap:\n",
    "                   hashmap[i+j] += 1\n",
    "                else:\n",
    "                    hashmap[i+j] = 1\n",
    "        \n",
    "        count = 0\n",
    "        for i in nums3:\n",
    "            for j in nums4:\n",
    "                index = -i-j\n",
    "                if index in hashmap:\n",
    "                    count += hashmap[index]\n",
    "        return count\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:\n",
    "        # 使用字典存储nums1和nums2中的元素及其和\n",
    "        hashmap = dict()\n",
    "        for n1 in nums1:\n",
    "            for n2 in nums2:\n",
    "                if n1 + n2 in hashmap:\n",
    "                    hashmap[n1 + n2] += 1\n",
    "                else:\n",
    "                    hashmap[n1 + n2] = 1\n",
    "\n",
    "        # 如果 -(n1+n2) 存在于nums3和nums4, 存入结果\n",
    "        count = 0\n",
    "        for n3 in nums3:\n",
    "            for n4 in nums4:\n",
    "                key = -(n3 + n4)\n",
    "                if key in hashmap:\n",
    "                    count += hashmap[key]\n",
    "        return count"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
